package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/decode-ways/description/
 * @create 2025/8/26 10:58
 * @since JDK17
 */

public class Solution02 {
    static int[] dp = new int[101];

    public int f1(char[] s, int cur) {
        if (cur == s.length) {
            return 1;
        }
        if (s[cur] == '0') {
            return 0;
        }

        int ans = 0;
        ans += f1(s, cur + 1);
        if (cur + 1 < s.length && s[cur] >= '1' && s[cur] <= '2' && s[cur + 1] <= '6') {
            ans += f1(s, cur + 2);
        }
        return ans;
    }

    public int f2(char[] s, int cur) {
        if (cur == s.length) {
            return 1;
        }
        if (s[cur] == '0') {
            return 0;
        }
        if (dp[cur] != -1) {
            return dp[cur];
        }
        int ans = 0;
        ans += f2(s, cur + 1);
        if (cur + 1 < s.length) {
            int a = (s[cur] - '0') * 10 + s[cur + 1] - '0';
            if (a <= 26) {
                ans += f2(s, cur + 2);
            }
        }
        return dp[cur] = ans;
    }

    public int f3(char[] s) {
        dp[s.length - 1] = s[s.length - 1] == '0' ? 0 : 1;
        dp[s.length] = 1;
        for (int i = s.length - 2, t; i >= 0; i--) {
            if (s[i] == '0') {
                continue;
            }
            dp[i] += dp[i + 1];
            t = (s[i] - '0') * 10 + s[i + 1] - '0';
            if (t <= 26) {
                dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
    public int numDecodings(String str) {
        char[] s = str.toCharArray();
        Arrays.fill(dp, 0, s.length, 0);
        return f3(s);
    }
}
